package com.since.data_structure.tree;

import com.since.data_structure.binarytree.node.Node;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created by Sincerity on 2020/5/21.
 * 描述：构建一个哈夫曼树
 *
 */
class HuffmanTree {
    public static void main(String[] args) {
        int[] array = {13, 8, 7, 3, 29, 6, 1};
        Node root = createHuffmanTree(array);
        root.preOder();
    }

    public static Node createHuffmanTree(int[] array) {
        //遍历array数组 将arr的每个元素构建成一个HuffmanTreeNode;
        List<HuffmanTreeNode> nodes = new ArrayList<>();
        for (int value : array) {
            nodes.add(new HuffmanTreeNode(value));
        }
        while (nodes.size() > 1) {
            //给节点进行排序
            Collections.sort(nodes);
//        System.out.println(nodes);
            //取出权值最小的二个节点构成一棵二叉树
            //最小的节点
            Node leftNode = nodes.get(0);
            //第二小的节点
            Node rightNode = nodes.get(1);
            //构成一棵新的二叉树
            HuffmanTreeNode parent = new HuffmanTreeNode(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;
            //从ArrayList删除处理过的二叉树节点
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //添加新的节点到arrayList中
            nodes.add(parent);
        }
        //返回哈夫曼树的最后一个数的节点
        return nodes.get(0);
    }

    static class HuffmanTreeNode extends Node implements Comparable<HuffmanTreeNode> {

        public HuffmanTreeNode(int value) {
            super(value);
        }

        @Override
        public String toString() {
            return "HuffmanTreeNode{" +
                    "value=" + value +
                    '}';
        }

        @Override
        public int compareTo(HuffmanTreeNode o) {
            return this.value - o.value;
        }
    }
}
